//https://leetcode.cn/problems/top-k-frequent-elements/description/?envType=study-plan-v2&envId=top-100-liked
//思路1:1.map+小顶堆实现；
//思路2:1.参考LFU算法实现；

#include <iostream>
#include <vector>
#include <queue>
#include <map>
#include <list>
#include <unordered_map>

using namespace std;

bool compare(const pair<int, int>& lhs, const pair<int, int>& rhs) {
            return lhs.second > rhs.second;
}

class Solution {
public:
    // 小顶堆
    class mycomparison {
        public:
            bool operator()(const pair<int, int>& lhs, const pair<int, int>& rhs) {
                return lhs.second > rhs.second;
            }
    };
    vector<int> topKFrequent(vector<int>& nums, int k) {
        // 要统计元素出现频率
        unordered_map<int, int> map; // map<num[i], 对应出现次数>
        for (int i = 0; i < nums.size(); i++) {
            map[nums[i]]++;
        }

        // 对频率排序
        // 定义一个小顶堆，大小为k
        priority_queue<pair<int, int>, vector<pair<int, int>>,mycomparison > pri_que;
        //这里必须使用指针声明，同时将类型带入，不如类好用的；
        //priority_queue<pair<int, int>, vector<pair<int, int>>,decltype(&compare) > pri_que(compare);
        //
        // 用固定大小为k的小顶堆，扫描所有频率的数值
        for (unordered_map<int, int>::iterator it = map.begin(); it != map.end(); it++) {
            pri_que.push(*it);
            if (pri_que.size() > k) {// 如果堆的大小大于k，则队列弹出，保证堆的大小一直为k
                pri_que.pop();
            }
        }

        // 找出前k个高频元素，因为小顶堆先弹出的是最小的，所以倒序输出到数组
        vector<int> ans(k);
        for (int i = k - 1; i >= 0; i--) {
            ans[i] = pri_que.top().first;
            pri_que.pop();
        }
        return ans;
    }
};

class Solution2 {
public:
    vector<int> topKFrequent(vector<int>& nums, int k) {
        std::map<int,int> key_count_map;
        std::map<int,std::list<int>,std::greater<int>> count_key_map;

        std::vector<int> res{};
        if(nums.size()<k ||k<1) return res;
        for(size_t i=0;i<nums.size();++i){
            if(key_count_map.count(nums[i])){
                int cur_nums = key_count_map[nums[i]];
                key_count_map[nums[i]]=cur_nums+1;
            }else{
                key_count_map[nums[i]]=1;
            }
        }
        for(auto t:key_count_map){
            count_key_map[t.second].emplace_back(t.first);
        }
        for(auto b_iter=count_key_map.begin();b_iter!=count_key_map.end();++b_iter){
            for(auto li:(*b_iter).second){
                if(res.size()==k){
                   break; 
                }
                res.emplace_back(li);
            }
        }
        return res;

    }
};